home *** CD-ROM | disk | FTP | other *** search
/ ETO Development Tools 1 / ETO Development Tools 1.iso / Essentials / MacApp Documentation / MacApp AppleLink Messages / MacApp.Tech$ 12⁄1⁄89 / 0372-UList for circular a-Jan90 < prev    next >
Encoding:
Text File  |  1990-01-12  |  3.0 KB  |  97 lines  |  [TEXT/GEOL]
  1. Item    4115113                         9-Jan-90        07:01
  2.  
  3. From:   POWERUP.DEV                     Power Up Software,PRT
  4.  
  5. To:     MACAPP.TECH$                    MacApp Technical
  6.  
  7. Sub:    UList for circular arrays
  8.  
  9. Attn:  MacApp.Tech$
  10. SentBy: James Plamondon
  11. Date   1/8/90
  12. Subject    UList for circular arrays
  13. From   James Plamondon
  14. To  MacApp.Tech$
  15.  
  16. Subject:   UList for circular arrays
  17. Gentlepersons,
  18.  
  19. I am faced with the need to write a class to implement circular arrays
  20. (described, among other places, in the book Data Structures and Algorithms, by
  21. Aho, Hopcroft, and Ullman, Addison-Wesley, 1982).
  22.  
  23. In brief, a circular array is one in which the 'virtual' first element may be
  24. something other than the actual first element, and in which, therefore, a
  25. given virtual index (i) refers to the actual array element denoted by the
  26. formula
  27.         actual array index = (i + fStart) MOD fSize;
  28. given that fSize is the number of elements in the array, fStart is the current
  29. first element, i is the requested virtual element, and in which both the
  30. actual and virtual elements are numbered from zero.
  31.  
  32. I happened to recall that TList is implemented using arrays, and that a method
  33. of that class, ComputeAddress(), is used to compute the offset to a given
  34. element.  The routine is a simple one, as seen below:
  35.  
  36. FUNCTION TList.ComputeAddress(index: INTEGER): LONGINT;
  37.  
  38.    VAR
  39.        p:                  LONGINT;
  40.        x:                  INTEGER;
  41.        item:               LONGINT;
  42.  
  43.    BEGIN
  44.    p := Ord(Handle(SELF)^) + fFirstOffset;             { Address of first
  45. physical item }
  46.  
  47.    IF fDeletions = 0 THEN                              { If no deletions,
  48. index to proper element }
  49.        ComputeAddress := p + BSL(index - 1, 2)         { p + ((index - 1) * 4)
  50. }
  51.    ELSE                                                { Ignore deleted
  52. elements }
  53.        BEGIN
  54.        x := index;
  55.        p := p - kElemSize;                             { we increment first in
  56. loop }
  57.  
  58.        WHILE x > 0 DO                                  { Skip elements until
  59. item is found }
  60.            BEGIN
  61.            p := p + kElemSize;
  62.            item := PLongInt(p)^;
  63.            IF item <> kDeletedElement THEN
  64.                x := x - 1;
  65.            END;
  66.  
  67.        ComputeAddress := p;
  68.        END
  69.    END;
  70.  
  71. I think that I can use TList to implment circular arrays by adding one field
  72. (fStart) and overriding one method, ComputeAddress().  fStart would contain
  73. the current virtual start of the array, as described above.  The new version
  74. of ComputeAddress() would be:
  75.  
  76. FUNCTION TCircularArray.ComputeAddress(index: INTEGER): LONGINT; OVERRIDE;
  77. BEGIN
  78. index := (index + fStart) MOD fSize;
  79. ComputeAddress := INHERITED ComputeAddress(index);
  80. END;
  81.  
  82. Does anybody see any reason why this scheme shouldn't work?  Or, does anyone
  83. know who wrote the TList class, so that I can ask that person directly?
  84.  
  85. Looking forward to your responses, I am
  86.  
  87. Yours,
  88.  
  89. James Plamondon
  90. Software Engineer
  91. PowerUp! Software
  92. 2929 Campus Drive, Suite 300
  93. San Mateo, CA  94403
  94. (415) 345-5900 x351
  95. AppleLink: PowerUp.Eng
  96.  
  97.